package segmentTreeWithLazy;

//线段树节点
class Tree {
	public int l; // 节点表示区间的左界
	public int r; // 节点表示区间的右届
	public int d; // 节点数据
	public int lz = -1; // lazy标记，-1表示未设置

	public Tree(int l, int r) {
		this.l = l;
		this.r = r;
	}
	//此部分解题时可不要
	public String toString() {
		return String.format("%d[lz:%d]", this.d, this.lz);
	}
}

public class Main {
	// 数据长度
	public static int N = 10;
	// 线段树原数组，下标从1开始计算
	public static int[] a = { 0, 1, 4, 5, 8, 6, 2, 3, 9, 10, 7 };
	// 线段树，数组表示，长度必须为原数组4倍
	public static Tree[] t = new Tree[N * 4];
	// 返回左儿子编号，参数p为父节点编号
	public static int lc(int p) {
		// 左儿子编号p*2
		return p << 1; // 位运算提高效率
	}
	// 返回右儿子编号，参数p为父节点编号
	public static int rc(int p) {
		// 右儿子编号p*2+1
		return p << 1 | 1; // 位运算提高效率
	}
	// 构建线段树
	// 参数p节点编号
	// 参数l，r表示节点p指向的区间[l,r]
	public static void build(int p, int l, int r) {
		// 实例化节点
		t[p] = new Tree(l, r);
		// l==r则当前节点为叶子，直接存值
		// 叶子节点的l对应原数据的下标
		if (l == r) {
			t[p].d = a[l];
			return;
		}
		// 折半找区间[l,r]的中点
		int mid = (l + r) >> 1;
		int lc = lc(p);
		int rc = rc(p);
		// 左儿子递归建树
		build(lc, l, mid);
		// 右儿子递归建树
		build(rc, mid + 1, r);
		// 从下往上传递区间值，放入节点
		// 此处决定线段树维护区间和或最大值或最小值
		pushUp(p);
	}

	// 从下往上传递区间值，放入节点
	// 此处的p是叶子节点
	private static void pushUp(int p) {
		// 维护区间和情况
		t[p].d = t[lc(p)].d + t[rc(p)].d;
		// 维护最小值情况
		// t[p].d = Math.min(t[lc(p)].d,t[rc(p)].d);
		// 维护最大值情况
		// t[p].d = Math.max(t[lc(p)].d, t[rc(p)].d);
	}

	// 区间更新、查询与懒操作部分代码
	// 设置lazy标记
	// 参数p节点编号
	// 参数v，每个子节点修改后的值
	public static void lazy(int p, int v) {

		// 维护区间和的情况，节点值应设置为懒标记值（区间每个点修改后的值）乘区间长度（r-l+1）
		t[p].d = v * (t[p].r - t[p].l + 1);

		// 维护区间最大值和最小值的情况
		// t[k].d = v;
		
		//标记lazy
		t[p].lz = v;
	}

	// 向下传递懒标记
	// 参数p节点编号
	public static void pushDown(int p) {

		lazy(lc(p), t[p].lz); // 下传左子节点
		lazy(rc(p), t[p].lz); // 下传右子节点
		// 清除自身lazy标记（还原为-1）
		t[p].lz = -1;
	}

	// 区间更新（lazy标记）
	// 参数p节点编号
	// 参数l，r表示将[l,r]区间更新为v
	public static void update(int p, int l, int r, int v) {
		// 找到了[l,r]子区间节点
		if (t[p].l >= l && t[p].r <= r) {
			// 更新节点值并设置lazy
			lazy(p, v);
			return;
		}

		// [l,r]和节点表示区间有交集的情况
		// 让节点的左右子树去处理
		// 当前节点值的更新是在本方法最后一行回溯时做的
		if (t[p].lz != -1) {
			// 如果当前节点有lazy标记则下传给子树
			pushDown(p);
		}

		// 折半找区间[t[p].l,t[p].r]的中点
		int mid = (t[p].l + t[p].r) >> 1;
		int lc = lc(p); // 左子节点下标
		int rc = rc(p); // 右子节点下标

		if (l <= mid)
			update(lc, l, r, v); // 左子树更新

		if (r > mid)
			update(rc, l, r, v); // 右子树更新

		// 从下往上更新区间值，放入节点
		// 此处决定线段树维护区间和或最大值或最小值
		pushUp(p);
	}

	// 查询线段树（带lazy标记的情况）
	// 参数p节点编号
	// 参数l，r表示求解的（区间和或最大值或最小值）区间[l,r]
	public static int queryl(int p, int l, int r) {
		// 1、查询区间覆盖节点区间，返回节点值（区简解）
		if (t[p].l >= l && t[p].r <= r) {
			return t[p].d;
		}

		// [l,r]和节点表示区间有交集的情况
		// 让节点的左右子树去处理
		if (t[p].lz != -1) {
			// 如果当前节点有lazy标记则下传给子树
			pushDown(p);
		}

		// 折半找节点区间[t[p].l,t[p].r]的中点
		int mid = (t[p].l + t[p].r) >> 1;
		// 计算节点的左右子节点编号
		int lc = lc(p);
		int rc = rc(p);

		// ans变量保存区间[l,r]答案（查询区间最大值）
		// int ans = Integer.MIN_VALUE;
		// ans变量保存区间[l,r]答案（查询区间最小值）
		// int ans=Integer.MAX_VALUE;
		// ans变量保存k节点，区间[l,r]答案（查询区间和）
		int ans = 0;

		// 查询区间最大值的情况
		// l与左子树有重叠，则进入左子树递归查询
//		if (l <= mid)
//			ans = Math.max(ans, queryl(lc, l, r));
//		// r与右子树有重叠，则进入左子树递归查询
//		if (r > mid)
//			ans = Math.max(ans, queryl(rc, l, r));

		// 查询区间最小值的情况
		// l与左子树有重叠，则进入左子树递归查询
//			if(l<=mid)
//				ans = Math.min(ans,queryl(lc,l,r));
//			//r与右子树有重叠，则进入左子树递归查询
//			if(r>mid)
//				ans = Math.min(ans,queryl(rc,l,r));

		// 查询区间和的情况
		// l与左子树有重叠，则进入左子树递归查询
		if (l <= mid)
			ans += queryl(lc, l, r);
		// r与右子树有重叠，则进入左子树递归查询
		if (r > mid)
			ans += queryl(rc, l, r);

		return ans;
	}

	public static void main(String[] args) {
		// 构建线段树
		build(1, 1, 10);

		System.out.println("查询区间[7,10]:");
		System.out.println(queryl(1, 7, 10));

		System.out.println("查询区间[5,10]:");
		System.out.println(queryl(1, 5, 10));

		System.out.println("修改区间[3,7]的值为12:");
		update(1, 3, 7, 12);

		System.out.println("查询区间[7,10]:");
		System.out.println(queryl(1, 7, 10));

		System.out.println("查询区间[5,10]:");
		System.out.println(queryl(1, 5, 10));

		System.out.println("查询区间[1,3]:");
		System.out.println(queryl(1, 1, 3));

		System.out.println("修改区间[1,5]的值为10:");
		update(1, 1, 5, 10);

		System.out.println("查询区间[7,10]:");
		System.out.println(queryl(1, 7, 10));

		System.out.println("查询区间[5,10]:");
		System.out.println(queryl(1, 5, 10));

		System.out.println("查询区间[1,3]:");
		System.out.println(queryl(1, 1, 3));
	}

}
